{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 测试"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "vscode": {
     "languageId": "c++"
    }
   },
   "source": [
    "快速开根号算法通常用于计算平方根的近似值，尤其是在性能要求较高的场景中（如实时图形渲染或嵌入式系统）。以下是几种常见的快速开根号算法：\n",
    "\n",
    "---\n",
    "\n",
    "### 1. **牛顿迭代法（Newton's Method）**\n",
    "牛顿迭代法是一种高效的数值方法，用于近似求解方程的根。对于平方根，可以通过迭代逼近。\n",
    "\n",
    "#### 公式：\n",
    "给定一个数 \\( a \\)，求解 \\( \\sqrt{a} \\) 等价于求方程 \\( f(x) = x^2 - a = 0 \\) 的根。牛顿迭代公式为：\n",
    "\\[\n",
    "x_{n+1} = x_n - \\frac{f(x_n)}{f'(x_n)} = x_n - \\frac{x_n^2 - a}{2x_n} = \\frac{x_n + \\frac{a}{x_n}}{2}\n",
    "\\]\n",
    "\n",
    "#### 实现：\n",
    "```python\n",
    "def sqrt_newton(a, tolerance=1e-10, max_iterations=1000):\n",
    "    if a < 0:\n",
    "        raise ValueError(\"Input must be non-negative\")\n",
    "    if a == 0:\n",
    "        return 0\n",
    "    x = a  # 初始猜测值\n",
    "    for _ in range(max_iterations):\n",
    "        next_x = 0.5 * (x + a / x)\n",
    "        if abs(next_x - x) < tolerance:\n",
    "            return next_x\n",
    "        x = next_x\n",
    "    return x\n",
    "```\n",
    "\n",
    "#### 特点：\n",
    "- 收敛速度快，精度高。\n",
    "- 适合高精度计算。\n",
    "\n",
    "---\n",
    "\n",
    "### 2. **快速平方根倒数算法（Fast Inverse Square Root）**\n",
    "这是经典的快速算法，最初出现在《雷神之锤 III》的源代码中，用于计算 \\( \\frac{1}{\\sqrt{a}} \\)。\n",
    "\n",
    "#### 公式：\n",
    "通过位操作和牛顿迭代法结合，快速计算平方根倒数。\n",
    "\n",
    "#### 实现（C语言风格）：\n",
    "```c\n",
    "float fast_inverse_sqrt(float number) {\n",
    "    const float threehalfs = 1.5F;\n",
    "    float x2 = number * 0.5F;\n",
    "    float y = number;\n",
    "\n",
    "    // 位操作\n",
    "    int i = *(int *)&y;          // 将浮点数解释为整数\n",
    "    i = 0x5f3759df - (i >> 1);   // 初始猜测值\n",
    "    y = *(float *)&i;            // 将整数解释为浮点数\n",
    "\n",
    "    // 牛顿迭代\n",
    "    y = y * (threehalfs - (x2 * y * y));  // 一次迭代\n",
    "    return y;\n",
    "}\n",
    "```\n",
    "\n",
    "#### 特点：\n",
    "- 速度极快，适合实时计算。\n",
    "- 精度较低，适用于图形渲染等场景。\n",
    "\n",
    "---\n",
    "\n",
    "### 3. **二分查找法**\n",
    "二分查找法是一种简单且稳定的方法，通过不断缩小范围逼近平方根。\n",
    "\n",
    "#### 实现：\n",
    "```python\n",
    "def sqrt_binary_search(a, tolerance=1e-10):\n",
    "    if a < 0:\n",
    "        raise ValueError(\"Input must be non-negative\")\n",
    "    if a == 0:\n",
    "        return 0\n",
    "    low, high = 0, a\n",
    "    if a < 1:\n",
    "        high = 1\n",
    "    while high - low > tolerance:\n",
    "        mid = (low + high) / 2\n",
    "        if mid * mid > a:\n",
    "            high = mid\n",
    "        else:\n",
    "            low = mid\n",
    "    return (low + high) / 2\n",
    "```\n",
    "\n",
    "#### 特点：\n",
    "- 实现简单，稳定性高。\n",
    "- 适合低精度需求。\n",
    "\n",
    "---\n",
    "\n",
    "### 4. **查表法（Lookup Table）**\n",
    "对于特定范围内的输入，可以预先计算平方根值并存储在表中，通过查表快速获取结果。\n",
    "\n",
    "#### 实现：\n",
    "```python\n",
    "import math\n",
    "\n",
    "# 预计算平方根表\n",
    "sqrt_table = {i: math.sqrt(i) for i in range(1000)}\n",
    "\n",
    "def sqrt_lookup(a):\n",
    "    if a < 0:\n",
    "        raise ValueError(\"Input must be non-negative\")\n",
    "    if a in sqrt_table:\n",
    "        return sqrt_table[a]\n",
    "    return math.sqrt(a)  # 超出表范围时使用标准方法\n",
    "```\n",
    "\n",
    "#### 特点：\n",
    "- 速度极快，但需要额外存储空间。\n",
    "- 适合输入范围有限且固定的场景。\n",
    "\n",
    "---\n",
    "\n",
    "### 5. **近似公式**\n",
    "对于不需要高精度的场景，可以使用近似公式快速计算平方根。\n",
    "\n",
    "#### 公式：\n",
    "\\[\n",
    "\\sqrt{a} \\approx \\frac{a + 1}{2} \\quad \\text{（适用于 \\( a \\) 接近 1 时）}\n",
    "\\]\n",
    "\n",
    "#### 实现：\n",
    "```python\n",
    "def sqrt_approximate(a):\n",
    "    if a < 0:\n",
    "        raise ValueError(\"Input must be non-negative\")\n",
    "    return (a + 1) / 2\n",
    "```\n",
    "\n",
    "#### 特点：\n",
    "- 计算速度快，但精度较低。\n",
    "- 适合对精度要求不高的场景。\n",
    "\n",
    "---\n",
    "\n",
    "### 总结\n",
    "- **牛顿迭代法**：高精度，适合通用场景。\n",
    "- **快速平方根倒数算法**：极快，适合实时计算。\n",
    "- **二分查找法**：简单稳定，适合低精度需求。\n",
    "- **查表法**：速度最快，但需要额外存储。\n",
    "- **近似公式**：速度最快，但精度最低。\n",
    "\n",
    "根据具体需求选择合适的算法！"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++14",
   "language": "C++14",
   "name": "xcpp14"
  },
  "language_info": {
   "name": "C++14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
